package com.ma.problem;



public class smallSum {
    /**
     * 小和问题
     * @param arr
     * @return
     */
    /**
     * 当问题涉及到一个数向左或右统计大小比较数量问题都可用归并
     */
    public static int run(int[] arr){
        if(arr==null||arr.length<2){
            return 0;
        }
        return process(arr,0,arr.length-1);
    }

    private static int process(int[] arr, int L, int R) {
        if(L==R){
            return 0;
        }
        int mid=L+((L-R)>>1);
        return process(arr,L,mid)
                +process(arr,mid+1,R)
                +marge(arr,L,mid,R);
    
    }

    private static int marge(int[] arr, int L, int M, int R) {
        int[] help=new int[R-L+1];
        int i=0
                ,p1=L//左组起始位置
                ,p2=M+1//右组起始位置
                ;
        int sum=0;
        //在不出界的前提下将小的扔给help
        while (p1<=M&&p2<=R){
            sum+=arr[p1]<arr[p2]?(R-p2+1)*arr[p1]:0;
            /*
            因为方向是向右找比较起来大的
            所以相等时优先将右赋值给help
            如：
            12223  222234
             ^     ^
            help: 12
            12223  222234
             ^      ^
            help: 122
            一直到
            12223  222234
             ^         ^
            help: 122222
            这样才会找到最近比左大的右组数
            赋值优先级取决于比较方向
            */

            help[i++]=arr[p1]<arr[p2]?arr[p1++]:arr[p2++];
        }
        //一旦有出界执行下面，将没出界剩下的赋给help
        while (p1<=M){
            help[i++]=arr[p1++];
        }
        while (p2<R){
            help[i++]=arr[p2++];
        }
        for(i=0;i<help.length;i++){
            arr[L+i]=help[i];
        }
        return sum;
    }







}
